package com.andnnl.shudu;

/**
 * Created by chenss on 2017/11/14.
 */
public class ShuDu {
    int count = 0;
    int times = 0;//次数
    int level = 0;//层数

    public static void main(String[] args) {
        test2();
    }

    private static void test1() {
        int[] xx = {12, 13, 14, 15, 16, 17, 18, 19, 20};
        int arr[][] = new int[3][3];
        int a = 2;
        int b = 3 / 2;
        for (int i = 1; i <= 9; i++) {
            arr[a++][b++] = xx[i - 1];
            if (0 == i % 3) {
                a = a - 2;
                b = b - 1;
            } else {
                a = a % 3;
                b = b % 3;
            }
        }
        System.out.println("output:");
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.print("\n");
        }
    }

    private static void test2() {
//        for(int i=0;i<9;i++)
//            for(int j=0;j<9;j++)
//                a[i][j]=;
        new ShuDu().start();
    }

//    static String source = ""
//            + "7 0 0 1 4 8 0 0 0"
//            + "3 0 0 0 0 6 0 0 0"
//            + "6 0 9 0 0 2 0 0 0"
//            + "0 0 0 0 1 0 2 0 0"
//            + "5 7 0 0 0 0 9 0 0"
//            + "0 0 0 7 0 0 0 6 0"
//            + "0 0 8 2 0 0 0 0 1"
//            + "0 0 4 0 0 0 0 0 0"
//            + "0 6 0 0 0 0 0 4 8";

//    static String source = ""
//            + "9 6 0 0 0 0 0 0 0 "
//            + "0 0 0 0 4 2 0 0 3 "
//            + "0 0 0 0 0 0 0 9 8 "
//            + "4 0 0 2 0 0 0 0 0 "
//            + "0 1 8 0 7 0 0 0 0 "
//            + "0 0 3 0 0 9 0 0 0 "
//            + "0 3 1 0 0 8 0 6 0 "
//            + "6 0 0 0 0 5 0 0 0 "
//            + "0 2 0 0 0 1 4 0 0 ";

    //5个解
//    static String source = ""
//            + "9 0 0 0 0 5 0 4 0 "
//            + "0 0 0 0 0 1 5 0 0 "
//            + "3 0 0 0 0 0 0 0 9 "
//            + "4 0 0 0 0 0 0 0 0 "
//            + "0 1 7 0 0 0 0 0 0 "
//            + "0 0 3 4 0 0 0 0 2 "
//            + "0 5 2 0 3 0 0 8 6 "
//            + "0 0 0 0 0 7 3 0 0 "
//            + "0 0 0 1 8 6 9 0 0 ";

    //test 3链接
//    static String source = ""
//            + "0 6 0 4 0 0 0 5 0 "
//            + "9 0 1 0 0 0 0 4 0 "
//            + "0 0 0 1 0 0 7 0 9 "
//            + "0 0 0 6 0 0 0 2 0 "
//            + "0 0 8 0 0 3 0 0 6 "
//            + "0 7 0 0 4 0 0 0 0 "
//            + "2 0 3 0 8 0 0 0 0 "
//            + "0 5 0 0 7 0 0 1 0 "
//            + "0 8 0 0 0 0 9 0 5 ";
    //test 无解
//    static String source = ""
//            + "3 0 0 4 0 0 0 0 7 "
//            + "0 0 0 0 0 0 1 0 0 "
//            + "0 0 0 1 6 0 4 8 0 "
//            + "2 0 4 0 0 3 0 0 0 "
//            + "0 0 9 0 8 0 5 0 0 "
//            + "0 0 0 6 0 0 8 0 9 "
//            + "0 5 7 0 1 9 0 0 0 "
//            + "0 0 8 0 0 0 0 0 2 "
//            + "9 0 0 0 0 7 0 0 8 ";

//    static String source = ""
//            + "0 0 0 0 0 0 0 0 0 "
//            + "1 3 4 0 0 0 0 0 0 "
//            + "2 0 5 0 0 9 0 0 7 "
//            + "6 0 1 0 4 0 9 0 0 "
//            + "0 7 0 0 2 0 0 3 0 "
//            + "0 0 3 0 8 0 6 0 5 "
//            + "9 0 0 7 0 0 1 0 4 "
//            + "0 0 0 0 0 0 8 6 2 "
//            + "0 0 0 0 0 0 0 0 0 ";
//    static String source = ""
//            + "3,0,0,4,0,0,0,0,7"
//            + "0,0,0,0,0,0,1,0,0"
//            + "0,0,0,1,6,0,4,8,0"
//            + "2,0,4,0,0,3,0,0,0"
//            + "0,0,9,0,8,0,5,0,0"
//            + "0,0,0,6,0,0,8,0,9"
//            + "0,5,7,0,1,9,0,0,0"
//            + "0,0,8,0,0,0,0,0,0"
//            + "9,0,0,0,0,7,0,0,8";

    static String source = ""
            + "0 0 8  0 7 4  0 0 5"
            + "0 0 4  0 8 0  1 6 0"
            + "0 0 0  5 0 0  0 0 0"
            + "0 8 0  0 0 0  0 4 0"
            + "0 0 0  0 0 0  5 0 7"
            + "9 2 0  0 0 5  0 0 0"
            + "0 4 0  0 0 0  9 0 0"
            + "0 0 0  7 0 8  0 0 1"
            + "1 0 6  2 0 0  8 0 0";
    //3解
//    static String source = ""
//            + "0 0 2 9 0 0 0 0 0 "
//            + "0 9 0 0 0 0 8 0 5 "
//            + "0 5 8 0 0 0 7 0 0 "
//            + "1 0 9 0 3 0 0 0 0 "
//            + "0 0 0 0 7 8 0 0 0 "
//            + "0 0 0 0 0 0 0 3 0 "
//            + "9 4 0 0 5 0 0 0 1 "
//            + "0 0 0 0 0 7 0 0 9 "
//            + "6 8 0 0 9 3 5 0 0 ";

    /**
     * 初始化数据
     *
     * @param source 空格分开的81个数字 0 表示待填
     * @return
     */
    private static int[][] init(String source) {
        source = source.replaceAll("[ ,]", "");
        int[][] data = new int[9][9];
        for (int i = 0; i < source.length(); i++) {
            //应该用source.charAt(i) - '0'
            int v = Integer.parseInt(source.charAt(i) + "");
            if (v != 0) {
//                data[i / 9][i % 9] = 1 << (v - 1);//存储2的倍数
                data[i / 9][i % 9] = v;//存储原始数
            }
        }
        return data;
    }

    private void start() {
        int[][] a = init(source);
        print(a);

        long t1 = System.currentTimeMillis();
//        SD(a, 0);
        SD2(a, 0);
        long t2 = System.currentTimeMillis();
        System.out.println("ms:" + (t2 - t1));
    }

    private boolean SD2(int[][] a, int n) {
        level++;
        int i = n / 9;
        int j = n % 9;
        if (a[i][j] == 0) {
            for (int k = 1; k <= 9; k++) {
                times++;
                if (test(a, i, j, k) == 1) {
                    a[i][j] = k;//设置值
                    if (n == 80) {
                        print(a);
//                        System.exit(0);
                        return true;
                    } else {
                        if(SD2(a, n + 1)){return true;}
                    }
                    a[i][j] = 0; //回溯
                }
            }
        } else {
            if (n == 80) {
                print(a);
//                System.exit(0);
                return true;
            } else {
                if(SD2(a, n + 1)){return true;}
            }
        }
        return false;
    }

    /**
     * 尝试填值求解
     *
     * @param b
     * @param n
     */
    void SD(int[][] b, int n) {
        int i, j;
        i = n / 9;
        j = n % 9;              //行列
        if (b[i][j] != 0) {        //如果该位置有数字
            if (n == 80)
                print(b);
            else
                SD(b, n + 1);
        } else {
            for (int k = 1; k <= 9; k++)
//            for (int k = 9; k >= 1; k--)
                if (test(b, i, j, k) == 1) //可以
                {
                    b[i][j] = k;
                    if (n == 80)
                        print(b);
                    else
                        SD(b, n + 1);
                    b[i][j] = 0; //回溯
                }
        }
    }

    //判断是否可以将第i行、第j列的数设为k
    int test(int[][] a, int i, int j, int k) {
        int m, n, xm, xn;

        //检查行是否有重复数字
        for (n = 0; n < 9; n++)
            if (a[i][n] == k)
                return 0;

        //检查列是否有重复数字
        for (m = 0; m < 9; m++)
            if (a[m][j] == k)
                return 0;

        //检查当前数字所有的9个格子里是否有重复的数字
        xm = (i / 3) * 3;
        xn = (j / 3) * 3;
        for (m = xm; m < xm + 3; m++)
            for (n = xn; n < xn + 3; n++)
                if (a[m][n] == k)
                    return 0;

//        int row1, col1, row2, col2;
//        for (int x = 0; x < 81 - 1; x++) {
//            row1 = x / 9;
//            col1 = x % 9;
//            for (int y = x + 1; y < 81; y++) {
//                row2 = y / 9;
//                col2 = y % 9;
//                if (row1 != row2 && col1 != col2 && a[row1][col1] == a[row2][col2] && a[row1][col1] != 0)
//                    return 0;
//            }
//        }


        return 1;
    }

    void print(int[][] a) {
        System.out.println("case: " + (count==0?"原题":count));
        count++;
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++) {
//                System.out.print(a[i][j] + "\t");
                System.out.print(a[i][j] + "  ");
//                if(j==2)System.out.println(" ");
//                if(j==5)System.out.println(" ");
//                if (j == 8) System.out.println("\n");
                if (j == 8) System.out.println("");
//                j==8&&i%3==2?printf("\n"):0;
            }
        System.out.println("times:"+times+" fun:"+level);
            times=0;level=0;
        System.out.println("--------------------------");

    }
}
